package heapTree;

import heapTree.nodes.Node;
import heapTree.nodes.StochasticNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;

public class QuadrinomialHeap<T> {
	public ArrayList<T> heapArray;

	public long numStochasticNodes = 0;

	public long numNodes = 0;

	public QuadrinomialHeap() {
		heapArray = new ArrayList<T>();
	}

	public QuadrinomialHeap(T[] objects) {
		this();
		for (int i = 0; objects != null && i < objects.length; i++) {
//			heapArray.add(objects[i]);
			if(objects[i]==null)
				continue;
			add(objects[i]);
		}

		List lst = heapArray;
		Collections.sort(lst);
	}

	public void add(T object) {
		HashMap<Integer, Object> h = containsStochasticNode(object);
		if (heapArray.isEmpty()) {
			heapArray.add(object);
			numStochasticNodes++;
			numNodes++;
			return;
		} else {
			if (h.get(new Integer(1)) == null) {
				T s = (T) h.get(new Integer(2));
				if (s == null) {
					throw new RuntimeException("StochasticNode is already in list and must exist");
				}
				heapArray.add(s);
				return;
			} else if ((h.get(new Integer(2)) == null)) {
				StochasticNode s = (StochasticNode) object;
				Node n = (Node) h.get(new Integer(1));
				if (n == null) {
					throw new RuntimeException("StochasticNode doesn't match, but its Node is already in list and must exist");
				}
				s.setNode(n);
				heapArray.add((T)s);
				numStochasticNodes++;
				return;
			} else
				throw new RuntimeException();
		}
	}

	/**
	 * Finds out if Stochastic Node or Node object is already present in heap array
	 * Helps to prevent duplicate objects in memory
	 * 
	 * @param object
	 * @return Hashmap containing nothing if not present,
	 * matching value Node object and 1 if Node is in list
	 * matching value StochasticNode object 2 if StochasticNode (which implies Node too) is in list
	 */
	public HashMap<Integer, Object> containsStochasticNode(T s) {
		HashMap<Integer, Object> h = new HashMap<Integer, Object>();
		if(s==null)
			return h;
		StochasticNode toInsertSN = (StochasticNode) s;
		for (int i = 0; i < heapArray.size(); i++) {
			StochasticNode arraySN = (StochasticNode) heapArray.get(i);
			// same exact object
			// should just point to already existing StochasticNode in index i
			if (arraySN.equals(toInsertSN)) {
				h.put(new Integer(2), arraySN);
				return h;
			}

			// not the same exact object because of object id, but all pertinent values are equal
			// should just point to already existing StochasticNode in index i
			if (arraySN.equalValues(toInsertSN)) {
				h.put(new Integer(2), arraySN);
				return h;
			}

			Node arrayN = (Node) arraySN.getNode();
			Node toInsertN = (Node) toInsertSN.getNode();
			if(arrayN==null && toInsertN!=null)
				continue;
			// same exact object
			// should just point to already existing StochasticNode in index i
			if ((arrayN==null && toInsertN==null) || arrayN.equals(toInsertSN)) {
				h.put(new Integer(1), arrayN);
				return h;
			}

			// not the same exact object because of object id, but all pertinent values are equal
			// should just point to already existing StochasticNode in index i
			if (arrayN.equalValues(toInsertN)) {
				h.put(new Integer(1), arrayN);
				return h;
			}
		}
		return h;
	}

	// An object comparison function for simplifying the
	// comparisons performed in the heapify methods.
	public static boolean less(Object obj1, Object obj2) {
		if (((Comparable) obj1).compareTo(obj2) < 0) {
			return true;
		} else {
			return false;
		}
	}

	// This getter for the internal heap array is for
	// testing purposes.
	public ArrayList<T> getHeapArray() {
		return heapArray;
	}

	public Object getMin() {
		if (heapArray != null && heapArray.size() > 0)
			return heapArray.get(0);
		else
			return null;
	}
}